1. Field of the Invention
The present invention relates to a division circuit and a graphic display processing apparatus capable of performing processing at a high speed.
2. Description of the Related Art
Computer graphics are often used in a variety of computer aided design (CAD) systems and amusement machines. Especially, along with the recent advances in image processing techniques, systems using three-dimensional computer graphics are becoming rapidly widespread.
In three-dimensional computer graphics, the color value of each pixel is calculated at the time of deciding the color of each corresponding pixel. Then, rendering is performed for writing the calculated value to an address of a display buffer (frame buffer) corresponding to the pixel.
One of the rendering methods is polygon rendering. In this method, a three-dimensional model is expressed as an composite of triangular unit graphics (polygons). By drawing the polygons as units, the colors of the pixels of the display screen are decided.
In polygon rendering, coordinates (x, y, z), color data (R, G, B, xcex1), homogeneous coordinates (s, t) of texture data indicating a composite image pattern, and a value of the homogeneous term q for the respective vertexes of the triangle in a physical coordinate system are input and processing is performed for interpolation of these values inside the triangle.
Here, the homogeneous term q is, simply stated, like an expansion or reduction rate. Coordinates in a UV coordinate system of an actual texture buffer, namely, texture coordinate data (u, v), are comprised of the homogeneous coordinates (s, t) divided by the homogeneous term q to give xe2x80x9cs/qxe2x80x9d and xe2x80x9ct/qxe2x80x9d which in turn are multiplied by texture sizes USIZE and VSIZE, respectively.
In a three-dimensional computer graphic system using such polygon rendering, the texture data is read from the texture buffer when drawing, and texture mapping is performed for applying the read texture data on the surface of the three-dimensional model.
Note that when texture mapping is performed on a three-dimensional model, the expansion/reduction rate of the image indicated by the texture data to be applied to each pixel changes.
The texture buffer is accessed by using the above texture coordinate data (u, v). At the time of reading the texture data from the texture buffer, xe2x80x9cs/qxe2x80x9d and xe2x80x9ct/qxe2x80x9d are calculated for all pixels to calculate the texture coordinate data (u, v). Accordingly, the number of division operations becomes enormous.
Note that in the three-dimensional computer graphic system of the related art, the above xe2x80x9cs/qxe2x80x9d and xe2x80x9ct/qxe2x80x9d are calculated by a division circuit explained below.
Below, the division circuit of the related art will be explained.
FIG. 4 is a view of the configuration of an example of a division circuit 300 of the related art.
As shown in FIG. 4, the division circuit 300 comprises absolute value processors 301 and 302, priority encoders 303 and 304, shift processors 305 and 306, a subtractor 307, a reciprocal calculator 308, a multiplier 309, a shift processor 310, and an encoder 311.
In the division circuit 300, the absolute value of a dividend s is normalized as shown in the equation (1) below for floating point representation of the input dividend s. When the sign of the dividend s is minus (negative), its index se and mantissa sm are generated based on the following equations (2) and (3).
xe2x80x83s=smxc3x972sexe2x80x83xe2x80x83(1)
sm=(xcx9cs+1)/{2**int(log2(xcx9cs+1))}xe2x80x83xe2x80x83(2)
Note that equation (2) is an operation for shifting xe2x80x9cxcx9cs+1xe2x80x9d by exactly a complement of 1 of xe2x80x9cint(log2(xcx9cs+1))xe2x80x9d that is, xe2x80x9cxcx9cint(log2(xcx9cs+1))xe2x80x9d, toward the most significant bit (MSB).
se=int{log2(xcx9cs+1)}xe2x80x83xe2x80x83(3)
Specifically, when the sign of the dividend s is minus, as shown in FIG. 5, the absolute value processor 301 shown in FIG. 4 calculates an inversion of the dividend s (Exclusive-OR), adds xe2x80x9c+1xe2x80x9d to the inversion result, finds a complement of 2 of the dividend s, that is, xe2x80x9cxcx9cs+1xe2x80x9d, and outputs the xe2x80x9cxcx9cs+1xe2x80x9d to the priority encoder 303 and the shift processor 305.
Note that, in the absolute number processor 301, the sign of the dividend s refers to a sign bit of the MSB of the dividend s. The sign is judged to be minus when the MSB is xe2x80x9c1xe2x80x9d and plus when the MSB is xe2x80x9c0xe2x80x9d.
A logarithm of 2 of xe2x80x9cxcx9cs+1xe2x80x9d, that is, xe2x80x9clog2(xcx9cs+1)xe2x80x9d, is found in the priority encoder 303. A integer value of the logarithm of 2, that is, xe2x80x9clog2(xcx9cs+1) xe2x80x9d, is output as an index se to the shift processor 305 and subtractor 307.
Then, the shift processor 305 shifts xe2x80x9cxcx9cs+1xe2x80x9d by exactly the complement of 1 of xe2x80x9cint(log2(xcx9cs+1))xe2x80x9d, that is, xe2x80x9cxcx9cint(log2(xcx9cs+1))xe2x80x9d, that is, the complement of 1 of the index se, toward the MSB to calculate the mantissa sm. The mantissa sm is output to the multiplier 309.
Also, in the above division circuit 300, when the sign of the dividend s is plus (positive), the absolute value processor 301, the priority encoder 303, and the shift processor 305 normalize the absolute value of the input dividend s and generate its index se and mantissa sm based on the following equations (4) and (5):
sm=s/{2**int(log2s)}xe2x80x83xe2x80x83(4)
Note that equation (4) is an operation for shifting xe2x80x9csxe2x80x9d by exactly the complement of 1 of xe2x80x9cint(log2s)xe2x80x9d, that is, xe2x80x9cxcx9cint(log2s)xe2x80x9d, toward the MSB.
se=int(log2s)xe2x80x83xe2x80x83(5)
Specifically, when the sign of the dividend s is plus, the dividend s passes through the absolute value processor 301 and is output to the priority encoder 303 and the shift processor 305.
Then, the priority encoder 303 finds the logarithm of 2 of the dividend s, that is, xe2x80x9clog2sxe2x80x9d. The integer value of the logarithm of 2, that is, xe2x80x9clog2sxe2x80x9d, that is, xe2x80x9cint(log2s)xe2x80x9d, is output as the index se to the shift processor 305 and the subtractor 307.
Then, the shift processor 305 shifts the dividend s by exactly the complement of 1 of xe2x80x9cint(log2s)xe2x80x9d, that is, xe2x80x9cxcx9cint(log2s)xe2x80x9d, toward the MSB and calculates the mantissa sm. The mantissa sm is output to the multiplier 309.
The absolute value processor 302, the priority encoder 304, and the shift processor 306 shown in FIG. 1 are used for calculating the index qe and mantissa qm of the divisor q. The processing is the same as that of the above absolute value processor 301, priority encoder 303, and shift processor 305.
The reciprocal calculator 308 calculates the reciprocal of the mantissa qm of the divisor q and outputs the reciprocal xe2x80x9c1/qmxe2x80x9d to the multiplier 309.
The multiplier 309 multiplies the mantissa sm and the reciprocal of the mantissa qm, that is, xe2x80x9c1/qmxe2x80x9d, and outputs the multiplication result xe2x80x9csm/qmxe2x80x9d to the shift processor 310.
The subtractor 307 subtracts the index qe from the index se and outputs the subtraction result xe2x80x9csexe2x88x92qexe2x80x9d to the shift processor 310.
The shift processor 310 shifts the multiplication result xe2x80x9csm/qmxe2x80x9d from the multiplier 309 by exactly the number of bits indicated by the subtraction result xe2x80x9csexe2x88x92qexe2x80x9d from the subtractor 307 toward the MSB and outputs the shift operation result S310 to the encoder 311.
The encoder 311, based on the sign of the dividend s and the sign of the divisor q, adds xe2x80x9c1xe2x80x9d indicating minus to the one upper bit of the MSB of the shift operation result S310 when the two signs are different and outputs the result as the division result xe2x80x9cs/qxe2x80x9d. When the sign of the dividend s and the sign of the divisor q are the same, the encoder 311 adds xe2x80x9c0xe2x80x9d indicating plus to the one upper bit of the MSB of the shift operation result S310 and outputs the result as the division result xe2x80x9cs/qxe2x80x9d.
Summarizing the problem to be solved by the invention, in the above division circuit 300 of the related art shown in FIG. 4, the processing time of the path for finding xe2x80x9c1/qmxe2x80x9d from the divisor q is longer than the path for finding the mantissa sm from the dividend s by the amount of the processing in the reciprocal calculator 308. Therefore, in the multiplier 309, the processing is suspended after receiving the mantissa sm as an input until receiving xe2x80x9c1/qmxe2x80x9d as an input. Namely, the path for obtaining xe2x80x9c1/qmxe2x80x9d from the divisor q is a critical path of the operation in the division circuit 300.
Such suspension of the operation has a large effect on the above three-dimensional computer graphic system which calculates xe2x80x9cs/qxe2x80x9d and xe2x80x9ct/qxe2x80x9d for all pixels. This creates a bottleneck in increasing the speed of movement and improving the picture quality of the three-dimensional image displayed on a cathode ray tube (CRT).
An object of the present invention is to provide a division circuit which can perform division at a high speed by shortening the critical path of the division.
Another object of the present invention is to provide a graphic display processing apparatus which can increase a speed of movement and improve a picture quality of a three-dimensional image displayed on a display device.
To attain the above objects, according to a first aspect of the present invention, there is provided division circuit performing a log2 operation on complements of a dividend and divisor to calculate indexes for each, shifting the complements by the indexes, then calculating a reciprocal value of the result of shifting of the complement of the divisor by a reciprocal processing means, multiplying the result of shifting of the dividend with the calculated reciprocal value, shifting the multiplication result by exactly a shift amount corresponding to the indexes of the dividend and divisor, and calculating a result of division in a digital form, said division circuit comprising a complement processing means for outputting a complement of 1 of the divisor when the divisor is negative; an adding means for adding xe2x80x9c1xe2x80x9d to the output from the complement processing means and making the result of addition an absolute value when the divisor is negative; a logarithm processing means for calculating a logarithm of 2 of an output value of the complement processing means and calculating an integer value of the calculated logarithm; a shift processing means for shifting the absolute value according to the integer value; an MSB replacing means for making the calculation value of the shift processing means a mantissa when the MSB of the calculation value is xe2x80x9c1xe2x80x9d, making the calculation value with an MSB replaced with xe2x80x9c1xe2x80x9d the mantissa when the MSB of the calculation value is xe2x80x9c0xe2x80x9d, and outputting the mantissa to the reciprocal processing means; and a shift amount determining means for subtracting the integer value from the index of the dividend when the MSB of the calculation result of the shift processing means is xe2x80x9c1xe2x80x9d, subtracting the integer value plus xe2x80x9c1xe2x80x9d from the index of the dividend when the MSB of the calculation result of the shift processing means is xe2x80x9c0xe2x80x9d, and making the result of subtraction the shift amount.
Preferably, the operation in the adding means and the operation in the logarithm processing means are performed in parallel.
In the division circuit of the first aspect of the present invention, a complement of, for example, 2 is calculated for the divisor first, a logarithm of 2 is calculated for the complement of 2, and an index is calculated. Next, the complement of 2 is shifted by the index and a mantissa of the dividend is calculated.
In parallel with the above calculation for finding the mantissa of the dividend, a complement of 1 of the divisor is calculated by the complement processing means when the divisor is negative.
Next, the adding means adds 1 to the complement of 1 calculated by the above complement processing means. The result becomes the absolute number of the divisor.
Also, in parallel with the above calculation in the adding means, a logarithm processing means calculates an integer value of a logarithm of 2 of the complement of 1 calculated in the above complement processing means.
Next, a shift processing means shifts the absolute value of the divisor in accordance with the above integer value.
Next, in the MSB rewrite means, when the MSB of the calculation value of the above shift processing means is xe2x80x9c1xe2x80x9d, the calculation value is set as a mantissa of the divisor. When the MSB of the calculation value is xe2x80x9c0xe2x80x9d, the calculation value with the MSB replaced by xe2x80x9c1xe2x80x9d is set as the mantissa of the dividend. Then the mantissa of the above dividend is output to the reciprocal processing means.
In the shift amount determination means, when the MSB of the calculation value of the shift processing means is xe2x80x9c1xe2x80x9d, the above integer value is subtracted from the index of the above dividend. When the MSB of the calculation value of the shift processing means is xe2x80x9c0xe2x80x9d, an addition value obtained by adding xe2x80x9c1xe2x80x9d to the above integer value is subtracted from the index of the above dividend. The subtraction result is made the shift amount.
Next, in the reciprocal processing means, the reciprocal value of the mantissa of the dividend is calculated.
Then, the mantissa of the dividend and the reciprocal value of the mantissa output from the above reciprocal processing means are multiplied. The multiplication result is shifted by exactly the above shift amount to calculate the division result.
According to a second aspect of the present invention, there is provided a division circuit performing multiplication between a dividend and a reciprocal of a divisor by a floating point system, comprising a first absolute value processing means for outputting a complement of 2 of the dividend as a first absolute value when the dividend is negative and outputting the dividend as the first absolute value when the dividend is positive; a first logarithm processing means for calculating a logarithm of 2 of the first absolute value and calculating an integer value of the calculated logarithm as a first logarithmic; a first shift processing means for shifting the first absolute value by exactly an inverse value of the first logarithmic value toward an MSB to calculate a first mantissa; a complement processing means for outputting a complement of 1 of the divisor when the divisor is negative and outputting the divisor when the divisor is positive; an adding means for outputting an output from the complement processing means plus xe2x80x9c1xe2x80x9d as a second absolute value when the divisor is negative and outputting an output from the complement processing means as the second absolute value when the divisor is positive; a second logarithm processing means for calculating a logarithm of 2 of the output of the complement processing means and calculating an integer value of the calculated logarithm as a second logarithmic; a second shift processing means for shifting the second absolute value by exactly an inverse value of the second logarithmic value toward an MSB; an MSB replacing means for outputting a calculation result of the second shift processing means as a second mantissa when the MSB of the calculation result is xe2x80x9c1xe2x80x9d and outputting the calculation value with an MSB replaced by xe2x80x9c1xe2x80x9d as the second mantissa when the MSB of the calculation value is xe2x80x9c0xe2x80x9d; a subtracting means for subtracting the second logarithmic value from the first logarithmic value when the MSB of the calculation result of the second shift processing means is xe2x80x9c1xe2x80x9d and subtracting the second logarithmic value plus xe2x80x9c1xe2x80x9d from the first logarithmic value when the MSB of the calculation result of the second shift processing means is xe2x80x9c0xe2x80x9d; a reciprocal processing means for calculating a reciprocal of the second mantissa; a multiplying means for multiplying the first mantissa by the reciprocal of the second mantissa; and a third shift processing means for shifting a result of multiplication of the multiplying means by exactly a result of subtraction of the subtracting means toward the MSB.
Preferably, the operation In the adding means and the operation in the second logarithm processing means are performed in parallel.
According to a third aspect of the present invention, there is provided a graphic display processing apparatus expressing a three-dimensional model by a composite of unit graphics, dividing homogeneous coordinates (s,t) by a homogeneous term q by a division circuit of the first aspect of the invention, reading texture data indicating a pattern to be added to the unit graphics from a storing means by using a texture address according to s/q and t/q of the result of the division to draw a graphic, and determining a color of each pixel, the division circuit performing a log2 operation on complements of a dividend and divisor to calculate indexes for each, shifting the complements by the indexes, then calculating a reciprocal value of the result of shifting of the complement of the divisor by a reciprocal processing means, multiplying the result of shifting of the dividend with the calculated reciprocal value, shifting the multiplication result by exactly a shift amount corresponding to the indexes of the dividend and divisor, and calculating a result of division in a digital form, the division circuit comprising: a complement processing means for outputting a complement of 1 of the divisor when the divisor is negative; an adding means for adding xe2x80x9c1xe2x80x9d to the output from the complement processing means and making the result of addition an absolute value when the divisor is negative; a logarithm processing means for calculating a logarithm of 2 of an output value of the complement processing means and calculating an integer value of the calculated logarithm; a shift processing means for shifting the absolute value according to the integer value; an MSB replacing means for making the calculation value of the shift processing means a mantissa when the MSB of the calculation value is xe2x80x9c1xe2x80x9d, making the calculation value with an MSB replaced with xe2x80x9c1xe2x80x9d the mantissa when the MSB of the calculation value is xe2x80x9c0xe2x80x9d, and outputting the mantissa to the reciprocal processing means; and a shift amount determining means for subtracting the integer value from the index of the dividend when the MSB of the calculation result of the shift processing means is xe2x80x9c1xe2x80x9d, subtracting the integer value plus xe2x80x9c1xe2x80x9d from the index of the dividend when the MSB of the calculation result of the shift processing means is xe2x80x9c0xe2x80x9d, and making the result of subtraction the shift amount.
According to a fourth aspect of the present invention, there is provided a graphic display processing apparatus comprising a storing means for storing texture data comprised of image data to be added to a unit graphic forming a basic unit for expressing a shape for display; a polygon rendering data generating means for generating polygon rendering data including three-dimensional coordinates (x,y,z), R (red), G (green), B (blue) data, homogeneous coordinates (s,t), and a homogeneous term q for vertexes of the unit graphic; a pixel location judging means for judging whether each of a plurality of pixels to be simultaneously processed is located inside the unit graphic and generating validity indication data indicating validity when the pixel is located inside the unit graphic; an interpolation data generating means for interpolating polygon rendering data of vertexes of the unit graphic to generate interpolation data of a pixel located inside the unit graphic by; and a texture processing means for performing an operation for dividing homogeneous coordinates (s,t) included in the interpolation data of a pixel for which the validity indication data indicates validity, among the plurality of pixels to be simultaneously processed, by a homogeneous term q to produce xe2x80x9cs/qxe2x80x9d and xe2x80x9ct/qxe2x80x9d by a division circuit according to the first aspect of the invention and reading texture data from the storing means by using a texture address according to the xe2x80x9cs/qxe2x80x9d and the xe2x80x9ct/qxe2x80x9d; the division circuit of the texture processing means is a division circuit performing a log2 operation on complements of a dividend and divisor to calculate indexes for each, shifting the complements by the indexes, then calculating a reciprocal value of the result of shifting of the complement of the divisor by a reciprocal processing means, multiplying the result of shifting of the dividend with the calculated reciprocal value, shifting the multiplication result by exactly a shift amount corresponding to the indexes of the dividend and divisor, and calculating a result of division in a digital form, the division circuit comprising: a complement processing means for outputting a complement of 1 of the divisor when the divisor is negative; an adding means for adding xe2x80x9c1xe2x80x9d to the output from the complement processing means and making the result of addition an absolute value when the divisor is negative; a logarithm processing means for calculating a logarithm of 2 of an output value of the complement processing means and calculating an integer value of the calculated logarithm; a shift processing means for shifting the absolute value according to the integer value; an MSB replacing means for making the calculation value of the shift processing means a mantissa when the MSB of the calculation value is xe2x80x9c1xe2x80x9d, making the calculation value with an MSB replaced with xe2x80x9c1xe2x80x9d the mantissa when the MSB of the calculation value is xe2x80x9c0xe2x80x9d, and outputting the mantissa to the reciprocal processing means; and a shift amount determining means for subtracting the integer value from the index of the dividend when the MSB of the calculation result of the shift processing means is xe2x80x9c1xe2x80x9d, subtracting the integer value plus xe2x80x9c1xe2x80x9d from the index of the dividend when the MSB of the calculation result of the shift processing means is xe2x80x9c0xe2x80x9d, and making the result of subtraction the shift amount.